/**
 * 40. 组合总和 II
 * 
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用一次。
 * 
 * 说明：
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。 
 * 
 * 示例 1:
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 * 	[1, 7],
 * 	[1, 2, 5],
 * 	[2, 6],
 * 	[1, 1, 6]
 * ]
 * 
 * 示例 2:
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 * 	[1,2,2],
 * 	[5]
 * ]
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 */

package zw;

import java.util.ArrayList;
import java.util.List;

public class T40 {
	public static List<List<Integer>> combinationSum(int[] candidates, int target) {
		sort(candidates);
		ArrayList<Integer> res = new ArrayList<>(); 
		List<List<Integer>> resList = new ArrayList<>();
		combination(candidates, 0, target, res, resList);
		return resList;
    }
	
	private static void combination(int[] candidates,int index, int target, ArrayList<Integer> res, List<List<Integer>> resList) {
		if(target == 0) {
			resList.add(new ArrayList<Integer>(res));
			return;
		}
		for(int i = index; i < candidates.length; i++) {
			if(target >= candidates[i]) {
				if(i > index && candidates[i] == candidates[i-1]){
                    continue;
                }
				res.add(candidates[i]);
				combination(candidates, i+1 ,target-candidates[i], res, resList);

				res.remove(res.size()-1);
			} else {
				break;
			}
		}
	}

	private static int[] sort(int[] array) {
		for(int i = array.length; i > 0; i--) {
			for(int j = 1; j < i; j++) {
				if(array[j-1] > array[j]) {
					int tmp = array[j];
					array[j] = array[j-1];
					array[j-1] = tmp;
				}
			}
		}
		return array;
	}
	
	public static void main(String[] args) {
		System.out.print(combinationSum(new int[] {10,1,2,7,6,1,5}, 8).toString());
	}
}
